// stackwalker.h: Generic stackwalker.
//
// The Stackwalker class is an abstract base class providing common generic
// methods that apply to stacks from all systems.  Specific implementations
// will extend this class by providing GetContextFrame and GetCallerFrame
// methods to fill in system-specific data in a StackFrame structure.
// Stackwalker assembles these StackFrame strucutres into a CallStack.
//

#ifndef LONGKEY_BREAKPAD_PROCESSOR_STACKWALKER_H_
#define LONGKEY_BREAKPAD_PROCESSOR_STACKWALKER_H_

#include <set>
#include <string>

namespace longkey_breakpad
{
	class CallStack;
	class MinidumpContext;
	class SourceLineResolverInterface;
	struct StackFrame;
	class SymbolSupplier;
	class SystemInfo;

	using std::set;

	class Stackwalker
	{
	public:
		virtual ~Stackwalker() {}

		// Populates the given CallStack by calling GetContextFrame and
		// GetCallerFrame.  The frames are further processed to fill all available
		// data.  Returns true if the stackwalk completed, or false if it was
		// interrupted by SymbolSupplier::GetSymbolFile().
		bool Walk(CallStack *stack);

		// Returns a new concrete subclass suitable for the CPU that a stack was
		// generated on, according to the CPU type indicated by the context
		// argument.  If no suitable concrete subclass exists, returns NULL.
		static Stackwalker* StackwalkerForCPU(const SystemInfo *system_info,
			MinidumpContext *context,
			MemoryRegion *memory,
			const CodeModules *modules,
			SymbolSupplier *supplier,
			SourceLineResolverInterface *resolver);

		static void set_max_frames(u_int32_t max_frames) { max_frames_ = max_frames; }
		static u_int32_t max_frames() { return max_frames_; }

	protected:
		// system_info identifies the operating system, NULL or empty if unknown.
		// memory identifies a MemoryRegion that provides the stack memory
		// for the stack to walk.  modules, if non-NULL, is a CodeModules
		// object that is used to look up which code module each stack frame is
		// associated with.  supplier is an optional caller-supplied SymbolSupplier
		// implementation.  If supplier is NULL, source line info will not be
		// resolved.  resolver is an instance of SourceLineResolverInterface
		// (see source_line_resolver_interface.h and basic_source_line_resolver.h).
		// If resolver is NULL, source line info will not be resolved.
		Stackwalker(const SystemInfo *system_info,
			MemoryRegion *memory,
			const CodeModules *modules,
			SymbolSupplier *supplier,
			SourceLineResolverInterface *resolver);

		// This can be used to filter out potential return addresses when
		// the stack walker resorts to stack scanning.
		// Returns true if any of:
		// * This address is within a loaded module, but we don't have symbols
		//   for that module.
		// * This address is within a loaded module for which we have symbols,
		//   and falls inside a function in that module.
		// Returns false otherwise.
		bool InstructionAddressSeemsValid(u_int64_t address);

		// Scan the stack starting at location_start, looking for an address
		// that looks like a valid instruction pointer. Addresses must
		// 1) be contained in the current stack memory
		// 2) pass the checks in InstructionAddressSeemsValid
		//
		// Returns true if a valid-looking instruction pointer was found.
		// When returning true, sets location_found to the address at which
		// the value was found, and ip_found to the value contained at that
		// location in memory.
		template<typename InstructionType>
		bool ScanForReturnAddress(InstructionType location_start,
			InstructionType *location_found,
			InstructionType *ip_found) {
				const int kRASearchWords = 30;
				for (InstructionType location = location_start;
					location <= location_start + kRASearchWords * sizeof(InstructionType);
					location += sizeof(InstructionType)) {
						InstructionType ip;
						if (!memory_->GetMemoryAtAddress(location, &ip))
							break;

						if (modules_ && modules_->GetModuleForAddress(ip) &&
							InstructionAddressSeemsValid(ip)) {

								*ip_found = ip;
								*location_found = location;
								return true;
						}
				}
				// nothing found
				return false;
		}

		// Information about the system that produced the minidump.  Subclasses
		// and the SymbolSupplier may find this information useful.
		const SystemInfo *system_info_;

		// The stack memory to walk.  Subclasses will require this region to
		// get information from the stack.
		MemoryRegion *memory_;

		// A list of modules, for populating each StackFrame's module information.
		// This field is optional and may be NULL.
		const CodeModules *modules_;

	protected:
		// The SourceLineResolver implementation.
		SourceLineResolverInterface *resolver_;

	private:
		// Obtains the context frame, the innermost called procedure in a stack
		// trace.  Returns NULL on failure.  GetContextFrame allocates a new
		// StackFrame (or StackFrame subclass), ownership of which is taken by
		// the caller.
		virtual StackFrame* GetContextFrame() = 0;

		// Obtains a caller frame.  Each call to GetCallerFrame should return the
		// frame that called the last frame returned by GetContextFrame or
		// GetCallerFrame.  To aid this purpose, stack contains the CallStack
		// made of frames that have already been walked.  GetCallerFrame should
		// return NULL on failure or when there are no more caller frames (when
		// the end of the stack has been reached).  GetCallerFrame allocates a new
		// StackFrame (or StackFrame subclass), ownership of which is taken by
		// the caller.
		virtual StackFrame* GetCallerFrame(const CallStack *stack) = 0;

		// The optional SymbolSupplier for resolving source line info.
		SymbolSupplier *supplier_;

		// A list of modules that we haven't found symbols for.  We track
		// this in order to avoid repeatedly looking them up again within
		// one minidump.
		set<std::string> no_symbol_modules_;

		// The maximum number of frames Stackwalker will walk through.
		// This defaults to 1024 to prevent infinite loops.
		static u_int32_t max_frames_;
	};
}

#endif	// LONGKEY_BREAKPAD_PROCESSOR_STACKWALKER_H_